package com.skh.array;

import java.util.Arrays;

/**
 * @Author: skh
 * @Date: 2018/8/23 15:15
 * @Description: 三个数的最大乘积
 */
public class MaximumProductOfThreeNumbers {

    /*
    给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

    示例 1:

    输入: [1,2,3]
    输出: 6
    示例 2:

    输入: [1,2,3,4]
    输出: 24
    注意:

    给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
    输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
     */


    /*
    即先将数组排序，我们假设数组够长，那么可能数组最左边三个是绝对值比较大的三个负数，数组最大值肯定要求正数，
    那么则有两种可能：取最右边三个或者最左边两个乘最右边一个   ，最后比较这两种情况取最大值即为所要求的值
     */
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int max1 = nums[0] * nums[1] * nums[nums.length - 1];
        int max2 = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];

        return Math.max(max1, max2);
    }

    public int maximumProduct1(int[] nums) {
        int first_max = Integer.MIN_VALUE;
        int second_max = Integer.MIN_VALUE;
        int third_max = Integer.MIN_VALUE;

        int first_min =Integer.MAX_VALUE;
        int second_min = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > first_max) {
                third_max = second_max;
                second_max = first_max;
                first_max = nums[i];
            } else if (nums[i] > second_max) {
                third_max = second_max;
                second_max = nums[i];
            } else if (nums[i] > third_max) {
                third_max = nums[i];
            }

            if (nums[i] < first_min) {
                second_min = first_min;
                first_min = nums[i];
            } else if (nums[i] < second_min) {
                second_min = nums[i];
            }
        }

        int max = first_max * second_max * third_max;
        int min = first_max * first_min * second_min;

        return Math.max(max, min);

    }
}
